In recent years, security for preventing forgery and information leakage has become important with regard to mobile devices, IC (Integrated Circuit) cards and other devices. In that case, it is general that ID (Identification Data) is given to each device, and the ID is used in security management such as device authentication and encryption. With such security management, it is possible to achieve an effect such as that even if the security of a certain device is destroyed, impact of its influence on other devices can be prevented.
Usually, a mechanism for generating a unique ID to each individual is implemented not by software but by hardware, from a safety point of view. As the hardware, for example, a semiconductor device such as an LSI (Large-Scale Integration) is used. In that case, it is not realistic to change a manufacturing mask for each semiconductor chip. For this reason, a value of ID (hereafter, when referring to a value itself of ID, it is referred to as an ID value) is not embedded in a logic circuit or the like of the semiconductor chip, but is written into an NVRAM (Non-Volatile Random Access Memory) or is set by blowing a fuse on the semiconductor chip.
On the other hand, a method of physical attack, side channel attack or the like against semiconductor devices is making progress year after year, and accordingly risk of decryption or falsification of ID which is set by means of an NVRAM or a fuse is increasing.
In order to cope with such risk, sometimes used is an ID generation mechanism called PUF (Physical Unclonable Function) which is difficult to falsify, that is, excellent in tamper resistance. A PUF circuit is a circuit for implementing a PUF mechanism, which outputs a measurement result of a physical or electrical characteristic (hereafter, simply referred to as a “physical characteristic”) which is unique to each individual of LSI chips, such as difference in circuit speed caused by fabrication variability, as an ID value.
It is generally impossible to make a duplicate device having completely the same physical characteristic as that of the original one. Therefore, a PUF circuit employing difference in a physical characteristic between individuals is equipped with “unclonability”. Additionally, exact prediction of a physical characteristic value for each individual is also impossible. Accordingly, an ID value outputted by the PUF circuit is also equipped with “unpredictability” meaning impossibility to predict the value.
As a typical PUF, methods employing, as an ID value, difference between individuals in a physical characteristic, such as the oscillation frequency of a ring oscillator, the delay time difference of a circuit and the initial value of a memory just after power on, are disclosed in Japanese Patent Application Laid-Open No. 2011-123909 (hereafter, referred to as “Patent Document 1”), in G. Edward Suh, S. Devadas, “Physical Unclonable Functions for Device Authentication and Secret Key Generation”, DAC 2007, pp. 9-14 (hereafter, referred to as “Non-patent Document 1”), in S. Eiroa, I. Baturone, “Hardware authentication based on PUFs and SHA-3 2nd round candidates”, ICM 2010, pp. 319-322 (hereafter, referred to as “Non-patent Document 2”), and in M. Yu, S. Devadas, “Secure and Robust Error Correction for Physical Unclonable Functions”, IEEE Design and Test of Computers, Vol. 27, No. 1, pp. 48-65 (hereafter, referred to as “Non-patent Document 3”).
An input to a PUF is referred to as a challenge. An output the PUF returns to the challenge is referred to as a response. In view of the purpose of employing a PUF, responses to the same challenge are required to always be the same value for the same individual and to surely be different values for different individuals.
Hereafter, “obtainability of always the same response to the same challenge” is referred to as “response repeatability”, and “obtainability of surely different responses for different individuals” as “individual identifiability”.
However, in a real PUF, there may occur a phenomenon of the PUF returning different values to different entries of the same challenge even when the entries of the same challenge are made to the same individual. That is, a real PUF is not necessarily equipped with response repeatability. In this respect, Non-patent Document 3 discloses a method for coping with this problem by performing error correction so as to enable obtaining the same response to the same challenge.
In a PUF using LSI fabrication variability, an ID value generated by the PUF cannot be known before completion of the LSI fabrication, unlike in a method of setting an ID value into a nonvolatile memory or a fuse at a time of LSI fabrication. Furthermore, it is also impossible to control LSI fabrication in a manner of enabling the PUF to generate a specific ID value.
Therefore, it is necessary to check, after fabricating LSIs, whether each PUF embedded in the respective LSIs generates a different ID value from that of every other LSI having been fabricated in the past. However, the checking takes a lot of time because it needs to be performed on whole of the same type of LSIs with the same PUF structure embedded therein which have been fabricated in the past. If a PUF generating the same ID value as that of another one is found, an LSI with the PUF embedded therein cannot be shipped and accordingly needs to be scrapped. For this reason, the yield of an LSI with an embedded PUF is decreased. Consequently, the long checking time and the decrease in yield cause cost increase. Even if the LSIs pass the post-fabrication check, there still remains a problem arising from their PUFs' using a physical or electrical characteristic. That is, it is possible that, at a time of using the LSIs after their shipment, some PUF generates the same ID value as that of another owing to change in an operating condition such as temperature; that is, individual identifiability becomes impossible to secure.